package mashibing.freshman.class02;

/**
 * 假设有一个数组arr，用户总是频繁的查询arr中某一段的累加和
 * 你如何组织数据，能让这种查询变得便利和快捷？
 */
public class Code01_PreSum {
	/**
	 * 方案一：每次都加
	 */
	public static class RangeSum1 {

		private int[] arr;

		public RangeSum1(int[] array) {
			arr = array;
		}

		public int rangeSum(int L, int R) {
			int sum = 0;
			for (int i = L; i <= R; i++) {
				sum += arr[i];
			}
			return sum;
		}

	}

	/**
	 * 方案二：记录累加和 *
	 * L == 0 ： preSum[R]
	 * L ！= 0 ：preSum[R] - preSum[L - 1]
	 */
	public static class RangeSum2 {

		private int[] preSum;

		// 初始化，计算好数组的累加和
		public RangeSum2(int[] array) {
			int N = array.length;
			preSum = new int[N];
			preSum[0] = array[0];
			for (int i = 1; i < N; i++) {
				preSum[i] = preSum[i - 1] + array[i];
			}
		}

		public int rangeSum(int L, int R) {
			return L == 0 ? preSum[R] : preSum[R] - preSum[L - 1];
		}

	}

}
